1. Field of the Invention
The present invention generally relates to a technique for switching a cell, which is a fixed length packet, represented by an ATM cell. Particularly, the present invention relates to a technique incorporated in a large-sized ATM switch which is used for an ATM exchange and which demands high throughput. More particularly, the present invention relates to a technique of cell switching using cell-based routing while preserving cell sequence, and to a technique of distributing cell traffic effectively.
Further, the present invention relates to a technique of forming ATM switch hardware improving the efficiency of LSI circuits in the ATM switch so as to reduce to a minimum the number of the LSI circuits necessary for the ATM switch.
In the specification, a basic switch is used as a component of the ATM switch. In addition, a cell which is generated by dividing a cell will be called a short cell.
2. Description of the Related Art
In terms of ATM (asynchronous transfer mode), fixed-length cells are switched at high speed using a simplified protocol by hardware rather than by software. Thus, high-speed controllability and high-speed switching capability are required for the ATM switch in the ATM exchange. Thus, it is not enough to expand the switch size by expanding each basic switch for realizing a required switch size which increases. The required switch size increases as the number of lines to be accommodated increases. Therefore, a multi stage switch configuration in which the basic switches are connected to each other in a multi stage manner is necessary.
A conventional multi stage switch will be described with reference to FIG. 1. FIG. 1 is a block diagram showing the conventional multi stage ATM switch. The first stage has n n×m switches, the second stage has m n×n switches, and the third stage has n m×n switches. Conventionally, it has been known that a cross architecture in which three stages of basic switches are connected is effective for expanding the switch size.
The routing algorithm in the cross architecture can be classified as a connection-based routing or a cell-based routing. In terms of the connection-based routing, cells which constitute a same VC (Virtual Connection) are routed through the same route in a switch. On the other hand, in terms of the cell-based routing, cells which constitute the same VC are routed through different routes in the switch.
Cell routing examples are shown in FIG. 2 and FIG. 3 showing the case of the connection-based routing and the cell-based routing respectively. In the following, problems in using the routing algorithms will be described with reference to FIG. 2 and FIG. 3.
As shown in FIG. 2, in the case of the connection-based routing, cells constituting the same VC which are input in the ATM switch are switched through the same switching route. In the cross architecture having three-stages, traffic distribution is carried out by basic switches in the first stage and the second stage, and switching is carried out by the basic switches in the second stage and the third stage.
Thus, it is necessary to distribute traffic on a connection level in the ATM switch in order to distribute the load of the basic switches equally in the second stage. For this purpose, resource management of the basic switches in the second stage is necessary. In the resource management, for example, a basic switch in the second stage is determined for connections to route through. The connections go to the same switch in the third stage.
If the resource management is not carried out effectively, the load of the basic switches in the second stage gets out of balance resulting in generating some basic switches of a high-load condition. As a result of this, a link block occurs continually in the high-loaded switches and a state in which QOS (quality of service) is not satisfied occurs in the ATM.
FIG. 2 shows an example of the above-mentioned state. In FIG. 2, the load of the basic switch in the second stage gets out of balance in a connection route going to a basic switch OSW#1 so that the load of the basic switch TSW#1 becomes low and the load of the basic switch TSW#n becomes high resulting in cell discarding at the output link. In order to prevent such a load unbalance, intelligent resource management needs to be carried out. In the resource management, a statistical characteristic of link-level multiplexed VCs is predicted in consideration of temporal variation of the VCs, then the load balance is ensured probabilistically. There are various methods for the resource management. One such method is to monitor the load state of each link and determining a connection route on the basis of the load state. Another such method is to obtaining the load state of a link by calculating a characteristic of multiplexed data of each output link of the basic switch in the second stage on the basis of a reported parameter of a connection, and determine a route of the VC on the basis of the load state information.
However, in terms of the large-sized ATM switch, which is the target of the present invention, which switch has many high-speed links exceeding several tens of gigabits per second, the above-mentioned methods are not effective because the cost for the resource management increases in the ATM switch as a whole. Specifically, since the large-sized ATM switch has a large number of connections, the algorithm for calculating routes for cell transmission becomes very complicated. Therefore, the hardware for the route calculation increases and it becomes difficult to realize the large-sized ATM switch.
In addition, it may be considered that the ATM switch allows load unbalance by speeding up the inside of the ATM switch in order to avoid the complicated resource management. However, it is necessary to speed up the link speed of the ATM switch to a speed 3 times the input/output line speed. This is not a cost effective method because it is very difficult to form such a high-speed link between the basic switches.
As shown in FIG. 3, as for the cell-based routing, since it is possible for the cells to take different routes, the load distribution in the ATM switch can be realized without concern regarding the characteristic of multiplexed data. That is, as shown in FIG. 3, the internal block can be prevented in the routing network if the cells which are input to the ATM switch are distributed to each input port of the routing network with equal probability. In this case, a distribution network in the ATM switch is used.
However, since cells which form the same VC are switched through multiple routes in the ATM switch according to the cell-based routing, cells which have routed through different routes may have different delays depending on the load applied to each buffer on the route. Thus, the time of the cell transfer delay may vary from route to route, thereby a cell-sequence disorder may occur at the output of the ATM switch. Therefore, cell-resequencing is necessary for ensuring the cell sequence order.
For example, Gigabit switch carries out the cell resequencing in the output port (Turner: DESIGN OF A GIGABIT ATM SWITCH, IEEE INFOCOM'77). FIG. 4 shows the configuration. As shown in FIG. 4, a time stamp is added to an incoming cell by a time stamp part. Then, the cells are switched, and the cell waits in a buffer of the output port. The cell resequencing is carried out by sorting cells in the buffer. FIG. 5 shows cells waiting in the buffer as cells in a sorting range.
However, in order to carrying out the above-mentioned sorting, it is necessary to provide a large-scale sorting circuit at each output port of the ATM switch for sorting switched cells based on the time information. Since the ATM switch which has high-speed links needs to carry out the sorting on many routes, the size of the ATM switch should be limited, thereby scalability of the ATM switch can not be obtained. In addition, as for system construction, the ATM switch is not economical since it is necessary to provide a high-speed switching function in a switch function part and a sorting function on every output port separately.
Further, the above-mentioned cell sequence ensuring method has a disadvantage as mentioned below. FIG. 6 shows load dependence of a cell transfer delay distribution. In FIG. 6, the horizontal axis shows the delay time, and the vertical axis shows probability of the cell frequency corresponding to the delay time. As shown in the figure, as the load in the ATM switch increases, the distribution shifts to the direction of increasing delay time. The figure shows that a cell which is transferred with an infinite delay time exists in a finite probability. However, it is physically impossible to provide a sorter with an infinite window size, resulting in carrying out the cell sequence sorting by a sorter with a finite window size in consideration of economy. Thus, the window size ΔT, which defines a sorting range of the sorter, is determined probabilistically, giving up cell resequencing for cells with delay below a probability. Therefore, the sorter in the sorting part carries out cell resequencing with the window size ΔT.
However, an old cell out of the finite window may arrive depending on a load state in the ATM switch. In such a case, the sorter can not ensure the cell sequence. The reason for this is that the cell resequencing is carried out after switching, that is, after the cell sequence disorder occurs. That is to say, the cell resequencing method which uses the sorter at the output of the switch has a disadvantage that the cell sequence can not be ensured 100%.
Moreover, another method for preventing the cell sequence disorder is proposed in M. Collivignarelli et al., “System and Performance Design of the ATM Node UT-XC,” IEEE ISS'94, pp. 613-618, in which maximum delay time is added.
According to the method, the cell delay time is equalized for each cell by adding a predefined maximum delay time D to every cell input in the switch, thereby ensuring the cell sequence. Specifically, according to the method, when assuming D1 as the switching delay of a cell at the output of the switch, an additional delay time D2=D−D1 is added to the cell at the output. Thus, the cell sequence is ensured.
However, according to the above-mentioned method of adding maximum delay time, since the predefined worst delay time D is added to every input cell, a good delay characteristic can not be obtained even if an input load of the ATM switch is low. In addition, it is necessary to set the absolute delay time to the ATM switch in the order of several hundreds when an allowed input load is 0.9. Therefore, the hardware block for adding the maximum delay time becomes complicated so that it becomes difficult to realize the hardware. Further, it is necessary to measure the switching delay time of each cell at the input/output part with precision in order to add the delay time to a transferred cell accurately, resulting in complicating a cell delay time measuring circuit and a delay time adding circuit which are provided in the input/output part. The complexity is a disadvantage for realizing the hardware.
Moreover, it is a problem to accommodate a large number of input/output lines in such a high-speed ATM switch. FIG. 7 shows an example of an ATM switch of a 16×16 switch size. For example, when realizing the ATM switch which has the 16×16 switch size and 160-Gbit/s switching throughput (the highway speed is 10-Gbit/s which is 622 Mbit/s×20) and the number of high-speed input/output lines of an LSI chip for the ATM switch is limited to 300 pins at the maximum, an LSI chip of a 4×2 ((4+2)×2×20=240, with 50 control lines) can be realized when inputting high speed signal in parallel to the ATM switch. Therefor, 32 chips are necessary in order to realize a 160-G bit/s cross-point switch.
FIG. 8 shows an LSI chip configuration when transferring cells by splitting cells spatially. As shown in FIG. 8, when cells are split spatially by using a bit slicing technique, 160 G/3 throughput can be realized by one chip (16×2×(20/3)≈230, with 50 control lines). Therefore, a 160-G bits/s throughput can be realized with 3 chips at the minimum. In addition, hardware logic in the chip is used effectively since high speed lines for interconnecting between chips can be eliminated.
FIG. 9 shows an example of a cross-point switch using parallel inputs and FIG. 10 shows an example of a cross-point switch using the bit slicing. In the case of the cross-point switch using parallel inputs shown in FIG. 9, the LSI chip in the center of the cross-point handles relaying signals in higher proportion than switching signals. Therefore, there is a problem that an integration degree of the logic used for switching is low.
On the other hand, as for the example shown in FIG. 10 using the bit slice technique, it is possible to integrate the switching logic effectively because most hardware is used for switching.
When expanding the ATM switch size by using the bit slicing method, basic switches are connected, each basic switch having a cell splitting function and a cell synthesizing function. Therefore, the ATM switch can not make the most of the merit of the bit slicing method. In addition, since cell splitting and synthesizing are repeated in the ATM switch, the amount of overhead circuits for cell splitting and synthesizing increases, thereby control becomes complex and hardware increases. Therefore, the method is not an economical approach.